package pro.softzhang.algo.lc300;

import java.util.*;

public class LC347_TopKFrequentElements {
    public static void main(String[] args) {

    }

    static class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> num2Count = new HashMap<>();
            for (int num : nums) {
                num2Count.put(num, num2Count.getOrDefault(num, 0) + 1);
            }

            Queue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
            for (Map.Entry<Integer, Integer> entry : num2Count.entrySet()) {
                if(heap.size() < k) {
                    heap.offer(entry);
                    continue;
                }
                if(entry.getValue() > heap.peek().getValue()) {
                    heap.poll();
                    heap.offer(entry);
                }
            }

            int[] arr = new int[heap.size()];
            int i = 0;
            for (Map.Entry<Integer, Integer> entry : heap) {
                arr[i++] = entry.getKey();
            }
            return arr;
        }
    }
}
